The present invention relates generally to automatic vehicle navigational systems, and more particularly, to an automatic vehicle routing and recommendation system. Even more particularly, the present invention is directed to a system for choosing one of a plurality of potential vehicles in a fleet for routing the fleet vehicle over the shortest distance and/or time from a current location to a target point such as a fire or a passenger for a taxicab.
Systems exist for routing a vehicle, such as a taxicab or a fire truck, from a current location to a target location. However, such systems have the drawback that even with today""s high speed computers, the systems are unable to route or recommend, in real time, which of a plurality of vehicles would be able to reach the target location first.
For example, there is a large effort called the Military Tracking System (MTS) for the logistical support of 40,000 vehicles. The 40,000 vehicles are tracked using known GPS technology. Many of these 40,000 vehicles are constantly moving and their locations are constantly dynamically changing. Potentially, there could be 40,000 changing positions per second.
This problem is due to the fact that this can be a mathematically difficult problem to solve. For example, if there are 40,000 vehicles moving around within a street set network having 100,000 segments that pose for a classical operations research optimization, a linear optimization problem. A matrix would be created having 100,000 street segments which would be a 100,000 by 100,000 matrix. Even though the matrix may be sparsely populated, it would be impossible to calculate which of the 40,000 vehicles could reach the target location in real time.
Classically, the matrix would have to be built and the matrix would be inverted. A lot of work goes into how the matrix is created and how to make the matrix efficient and how to do the matrix inversion efficiently.
Accordingly, a need exists in the art for a system and method for recommending a route for one of a plurality of vehicles to a target location which is determinable in real time.
It is, therefore, an object of the present invention to provide an algorithm which can be solved in real time for providing a recommendation and routing of one of a plurality of vehicles to a target location in the shortest time/distance.
It is a further object of the present invention to eliminate most of the mathematical processing needed to solve an algorithm for recommending and routing a vehicle to a target location where the vehicle is chosen from a plurality of vehicles in a fleet.
These and other objects of the present invention are achieved by a method of recommending which of a plurality of vehicles should be routed from a present location to a target location on a tessellated map plane. The tessellated map plane overlays a street network and are divided into a plurality of tessellations. A plurality of dynamically changing vehicle locations representing a location of a vehicle are continuously stored with each of the vehicle locations being a present location and being within one of the plurality of tessellations. For each of the plurality of vehicles, a next tessellation is determined adjacent the tessellation within which the vehicle is located. If the second location is not located within the next tessellation, a further tessellation is determined until a tessellation is determined including the target location. One of the plurality of vehicles is selected which would travel the shortest distance from the present location to the target location.
Still other objects and advantages of the present invention will become readily apparent to those skilled in the art from the following detailed description, wherein the preferred embodiments of the invention are shown and described, simply by way of illustration of the best mode contemplated of carrying out the invention. As will be realized, the invention is capable of other and different embodiments, and its several details are capable of modifications in various obvious respects, all without departing from the invention. Accordingly, the drawings and description thereof are to be regarded as illustrative in nature, and not as restrictive.